Supply Chain Chaos 📉
Ships are arriving in a scrambled order. We need to calculate the Chỉ số Hỗn loạn (số lượng cặp đảo ngược) để tối ưu hóa bộ điều khiển giao thông AI.
Cặp đảo ngược là gì?
A pair of indices $(i, j)$ is an inversion if:
- $i < j$ (Tàu $i$ đến trước tàu $j$)
- $A[i] > A[j]$ (Tàu $i$ có mã định danh ưu tiên cao hơn)
Analysis 🔍
Dãy ví dụ: [2, 4, 1, 3, 5]
- ❌ (2, 1): 2 đến trước 1, nhưng 2 > 1
- ❌ (4, 1): 4 đến trước 1, nhưng 4 > 1
- ❌ (4, 3): 4 đến trước 3, nhưng 4 > 3
- Tổng hỗn loạn: 3 cặp đảo ngược
Thách thức
A brute force nested loop is $O(N^2)$.
for i in range(n):
for j in range(i+1, n): ...
for j in range(i+1, n): ...
For $N=100,000$, this takes ~10 billion ops. Kết quả: Vượt quá giới hạn thời gian.